import java.util.Arrays;

/**
 * @作者 钟先崟
 * @时间 2023-02-24 13:14
 * @说明 767. 重构字符串
 * 给定一个字符串 s ，检查是否能重新排布其中的字母，使得两相邻的字符不同。
 * 返回 s 的任意可能的重新排列。若不可行，返回空字符串 "" 。
 * 示例 1:
 * 输入: s = "aab"
 * 输出: "aba"
 */
public class Solution {
    public static void main(String[] args) {
        System.out.println(reorganizeString("aab"));
        System.out.println(reorganizeString("aaab"));
    }

    /**
     * 执行用时：
     * 1 ms
     * , 在所有 Java 提交中击败了
     * 76.56%
     * 的用户
     * 内存消耗：
     * 39.7 MB
     * , 在所有 Java 提交中击败了
     * 47.93%
     * 的用户
     * @param s
     * @return
     */
    public static String reorganizeString(String s) {
        int n = s.length();
        int[] letterCount = new int[26];
        int maxCount = 0;
        int maxCountI = 0;
        for (int i = 0; i < n; i++) {
            letterCount[s.charAt(i) - 'a']++;
            if (letterCount[s.charAt(i) - 'a'] > maxCount) {
                maxCount = letterCount[s.charAt(i) - 'a'];
                maxCountI = s.charAt(i) - 'a';
            }
        }
        char[] res = new char[n];
        if (letterCount[maxCountI] > (n + 1) / 2)
            return "";
        //先把最大的数填在偶数位置0,2,4......
        int i;
        for (i = 0; letterCount[maxCountI] > 0; i = i + 2) {
            res[i] = (char) (maxCountI + 'a');
            letterCount[maxCountI]--;
        }
        if (i % 2 == 0 && i >= n) i = 1;
        int index = 0;
        while (i < n && index < 26) {
            if (letterCount[index] > 0) {
                letterCount[index]--;
                res[i] = (char) (index + 'a');
                i = i + 2;
                if (i % 2 == 0 && i >= n) i = 1;
            } else index++;
        }
        return String.valueOf(res);
    }
}
